package com.rayboo.example.algorithm.sort;

import java.util.Arrays;

/**
 * 二分插入排序
 *
 * <p>二分（折半）插入排序是一种在直接插入排序算法上进行小改动的排序算法。
 * 其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。
 *
 * <p>https://www.jianshu.com/p/18e3847816d9
 */
public class BinaryInsertSort {

    public static void main(String[] args) {
        int[] arr = {10, 2, 13, 4, 5, 6, 17, 8, 0};
        System.out.println("排序前：\n" + Arrays.toString(arr));

        new BinaryInsertSort().sort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));
    }

    /**
     * 二分插入排序
     *
     * @param arr 数组
     */
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int low = 0, high = i - 1, mid;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (arr[mid] > temp) {
                    high = mid - 1;
                } else { // 元素相同时，也插入在后面的位置
                    low = mid + 1;
                }
            }

            if (i - low >= 0) System.arraycopy(arr, low, arr, low + 1, i - low);

            arr[low] = temp;
        }
    }
}
